package LeetCodeHot100TopInterview;

import java.util.*;

public class Q017_PhoneNumCombinations {
    //用静态变量会导致 leetcode 出 bug，leecode 多次调用 类变量不会重置 导致后续调用出现问题
    //解决 程序入口刷新
    static private List<String> ans = null;

    //电话号码字母组合
    //给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合 ==> 手机九键
    //暴力递归 转 dp
    public List<String> letterCombinations(String digits) {
        if (digits == null || digits.length() == 0){
            return new ArrayList<>();
        }
        //刷新
        ans = new ArrayList<>();
        char[] str = digits.toCharArray();

        //九键映射
        Map<Character, String[]> map = new HashMap<>();
        map.put('2', new String[]{"a", "b", "c"});
        map.put('3', new String[]{"d", "e", "f"});
        map.put('4', new String[]{"g", "h", "i"});
        map.put('5', new String[]{"j", "k", "l"});
        map.put('6', new String[]{"m", "n", "o"});
        map.put('7', new String[]{"p", "q", "r", "s"});
        map.put('8', new String[]{"t", "u", "v"});
        map.put('9', new String[]{"w", "x", "y", "z"});

        process(new StringBuilder(), str, 0, map);
        System.out.println(ans);
        return ans;
    }

    //返回可能的结果
    //广度优先递归
    public void process(StringBuilder sb, char[] str, int index, Map<Character, String[]> map){
        if (index == str.length){
            ans.add(sb.toString());
            return;
        }
        // == >String[]{
        String[] tag = map.get(str[index]);
        for (int i = 0; i < tag.length; i++) {
            sb = sb.append(tag[i]);
            process(sb, str, index + 1, map);
            sb.deleteCharAt(index);
        }
    }

    public static void main(String[] args) {
        Q017_PhoneNumCombinations fun = new Q017_PhoneNumCombinations();
        fun.letterCombinations("2");
    }
}

